package com.example.androidtraining_ahut2020.proj.util;

import java.util.List;
import java.util.Vector;

public class BruteSearcherCantoImp implements Searcher {


    public static void main(String[] args) {
        System.out.println(new BruteSearcherCantoImp().search(new int[]{3, 8, 3, 8}));
        // System.out.println(search(new int[]{1, 4, 2, 3}));
        //  System.out.println(search(new int[]{1, 1, 1, 1}));
    }


    /**
     * 确定搜索器的实现v1.1
     * 枚举运算符的种类,构造出后缀表达式
     *
     * @param arr2
     * @return
     */
    public List<String> search(int[] arr2) {
        List<String> ans = new Vector<String>();
        for (int i = 0; i < 7; i++) ans.add(new String(""));

        for (int x = 0; x < 4; x++)
            for (int y = 0; y < 4; y++)
                for (int z = 0; z < 4; z++) {
                    List<String> exp = new Vector<>();
                    exp.add(OPERATORS[x]);
                    exp.add(OPERATORS[y]);
                    exp.add(OPERATORS[z]);
                    for (int e : arr2) exp.add(Integer.toString(e));

                    for (int i = 0; i < FAC[7]; i++) {
                        int[] idx = codel(i, 7);
                        for (int j = 0; j < 7; j++) {
                            ans.set(j, exp.get(idx[j]));
                        }
                        //  System.out.println(ans);
                        if (Math.abs(PostExpression.eval(ans) - TARGET) < EPS) {
                            // System.out.println(ans);
                            return ans;
                        }
                    }
                }
        return null;
    }

    static final int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

    public static int[] codel(int x, int m) {
        int[] label = new int[m];
        int[] n = new int[m];
        int cnt;
        for (int i = 0; i < m; i++)
            label[i] = 1;
        for (int i = 0; i < m; i++) {
            cnt = x / FAC[m - 1 - i];
            x = x % FAC[m - 1 - i];
            for (int j = 0; j < m; j++) {
                if (label[j] == 0)
                    continue;
                if (cnt == 0) {
                    label[j] = 0;
                    n[i] = j;
                    break;
                }
                cnt--;
            }
        }
        return n;
    }

}
